#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>




typedef struct ListNode ListNode;
ListNode* fast, * slow;
int kthToLast(struct ListNode* head, int k) {
	slow = fast = head;
	while (k--)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->val;
}




typedef struct ListNode ListNode;
ListNode* fast, * slow;
int kthToLast(struct ListNode* head, int k) {
	slow = fast = head;
	while (k--)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->val;
}



typedef struct ListNode ListNode;
ListNode* fast, * slow;
int kthToLast(struct ListNode* head, int k) {
	slow = fast = head;
	while (k--)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->val;
}



typedef struct ListNode ListNode;
ListNode* fast, * slow;
int kthToLast(struct ListNode* head, int k) {
	slow = fast = head;
	while (k--)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->val;
}








//typedef struct ListNode ListNode;
//ListNode* fast, * slow;
//int kthToLast(struct ListNode* head, int k) {
//	slow = fast = head;
//	while (k--)
//	{
//		fast = fast->next;
//	}
//	while (fast)
//	{
//		fast = fast->next;
//		slow = slow->next;
//	}
//	return slow->val;
//}
//
//

struct ListNode {
	int val;
	struct ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};
typedef struct ListNode ListNode;

ListNode* MidNode(ListNode* phead)
{
	ListNode* fast, * slow;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}
ListNode* reverseList(ListNode* phead)
{
	ListNode* newhead = NULL;
	ListNode* cur = phead;
	ListNode* next = cur->next;

	while (cur)
	{
		next = cur->next;
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}

class PalindromeList {
public:
	bool chkPalindrome(ListNode* A) {

		ListNode* phead = A;
		ListNode* mid = MidNode(phead);
		ListNode* newphead = reverseList(phead);
		while (mid && A)
		{
			if (mid->val != A->val)
			{
				return false;
			}

			mid = mid->next;
			A= A->next;
		}

		return true;
	}
};






